﻿#pragma once
#include "Index.h"

/**
 * 搜索二维矩阵.
 * https://leetcode.cn/problems/search-a-2d-matrix/
 */
class Search2DMatrix
{
public:
    /**
     * 二分查找：这是该代码使用的查找算法。
     * 线性索引：这是在矩阵中查找元素的方式。
     * 矩阵：矩阵是搜索目标值的数据结构。
     * 目标值：目标值是要在矩阵中查找的值。
     *
     * 利用二分查找算法，在二维整型数组中查找目标整数。
     * 具体来说，首先将二维数组转化为一维数组，即将每一行拼接在一起形成一个新的数组。
     * 接着，对新数组进行二分查找，找到目标整数或者确定目标整数不在新数组中。
     */
    bool searchMatrix(std::vector<std::vector<int>>& matrix, int target)
    {
        if (matrix.empty() || matrix.front().empty())
            return false;
        _rowSize = matrix.size();
        _colSize = matrix.front().size();

        int left = 0, right = _rowSize * _colSize - 1;
        while (left <= right)
        {
            const int mid = (left + right) >> 1;
            const auto& midVal = matrixValueInLinearIndex(matrix, mid);
            if (midVal == target)
                return true;
            else if (midVal < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }
private:
    int& matrixValueInLinearIndex(std::vector<std::vector<int>>& matrix, int linearIndex)
    {
        const int row = linearIndex / _colSize;
        const int col = linearIndex % _colSize;
        return matrix[row][col];
    }
private:
    int _rowSize, _colSize;
};